package com.cqs.leetcode.search;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author lixiaowen
 * @create 2020-02-05
 */
public class SearchinRotatedSortedArrayII81 {

    static class Solution {
        public boolean search(int[] nums, int target) {
            if (nums == null || nums.length == 0) return false;
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] == target) return true;
                if (target < nums[mid]) {
                    //1. 左侧单调 右侧有旋转点
                    if (nums[left] < nums[mid]) {
                        //落在左侧
                        if (nums[left] <= target) {
                            right = mid - 1;
                        } else {//落在右侧
                            left = mid + 1;
                        }
                    }
                    //2. 右侧单调 左侧有旋转点
                    else if (nums[left] > nums[mid]) {
                        right = mid - 1;
                    }
                    //3. 相等 不能推断旋转点在那一侧不过,根据单调性可以知道有一测一定是直线
                    //注意case {1,3,1,1,1},{1,1,1,3,1}
                    else {
                        while (left <= mid && nums[left] == nums[mid]) {
                            ++left;
                        }
                        //右侧侧是直线
                        if (left < mid) {
                            right = mid - 1;
                        }
                        //左侧是直线 left = mid + 1
                    }
                } else {
                    if (nums[left] < nums[mid]) {
                        left = mid + 1;
                    } else if (nums[left] > nums[mid]) {
                        if (target <= nums[right]) {
                            left = mid + 1;
                        } else {
                            right = mid - 1;
                        }
                    } else {
                        while (left <= mid && nums[left] == nums[mid]) {
                            ++left;
                        }
                        if (left < mid) {
                            right = mid - 1;
                        }
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Map<int[], Integer> cases = new LinkedHashMap<>();
        int[] arr = new int[4];
        arr = new int[]{1, 3, 1, 1, 1};
        cases.put(new int[]{1, 3, 5}, 5);
        cases.put(new int[]{3, 5, 1}, 1);
        cases.put(Arrays.copyOf(arr, arr.length), 3);
        arr = new int[]{1, 1, 1, 3, 1};
        cases.put(Arrays.copyOf(arr, arr.length), 3);
        cases.put(new int[]{3, 2}, 2);
        cases.forEach((k, v) -> {
            boolean search = solution.search(k, v);
            System.out.println(ArraysUtils.formatInts(k) + "\t" + v + "\t" + search);
        });
        System.out.println();
    }
}
